Bohdan Stashynsky sinh ra trong một gia đình nông dân ở làng Borshchovychi (tiếng Ukraina: Борщовичи; tiếng Ba Lan: Barszczowice) quận Pustomyty tỉnh Lviv, Cộng hòa Ba Lan, không xa thành phố Lviv. Tháng 8/1939 tỉnh Lviv chuyển sang lãnh thổ Cộng hòa Xã hội chủ nghĩa Xô viết Ukraina theo Hiệp ước Xô-Đức.

Bohdan hoàn thành giáo dục phổ thông năm 1948, vào học tại Học viện Sư phạm Lviv. Gia đình của Stashynsky là những người theo chủ nghĩa dân tộc Ukraina, ủng hộ Quân đội nổi dậy Ukraina (UPA) chống Liên Xô. Ba chị gái của Bohdan là thành viên của tổ chức này. Năm 1950, Bohdan bị bắt vì đi du lịch mà không có vé trên phương tiện giao thông công cộng đến Lviv từ làng của anh ta. Sau khi đồng ý làm người cung cấp thông tin, anh được thả. Thông qua các chị gái của mình, anh đã thâm nhập vào hoạt động của UPA, và chuyển thông tin đến Bộ An ninh Liên Xô.